/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    bool evaluateTree(TreeNode* root) {
//        if (root->left == nullptr)
//        {
//            if (root->val == 0) return false;
//            else return true;
//        }
//
//        int left = evaluateTree(root->left);
//        int right = evaluateTree(root->right);
//        return root->val == 2 ? left | right : left & right;
//    }
//};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
//class Solution {
//public:
//    TreeNode* pruneTree(TreeNode* root) {
//        if (root == nullptr) return nullptr;
//        root->left = pruneTree(root->left);
//        root->right = pruneTree(root->right);
//        if (root->left == nullptr && root->right == nullptr && root->val == 0)
//        {
//            root = nullptr;
//        }
//        return root;
//    }
//};

//#include<bits/stdc++.h>
//using namespace std;
//int check(int n, int k)
//{
//    int sum = 0;
//    while (n != 0)
//    {
//        sum += n % k;
//        n /= k;
//    }
//    return sum;
//}
//int main()
//{
//    int ans = 0;
//    for (int i = 1; i <= 2024; i++)
//    {
//
//        if (check(i, 2) == check(i, 4)) ans++;
//    }
//    cout << ans;
//    return 0;
//}

//#include <iostream>
//using namespace std;
//const int N = 1e5 + 10;
//long long a[N], s[N];
//int main()
//{
//    int n = 0;
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        int x;
//        cin >> x;
//        s[i] = s[i - 1] + x;
//    }
//
//    long long mins = (long long)(1e18);
//    for (int l1 = 1; l1 < n; l1++)
//    {
//        for (int r1 = l1; r1 < n; r1++)
//        {
//            long long s1 = s[r1] - s[l1 - 1];
//            for (int l2 = r1 + 1; l2 <= n; l2++)
//            {
//                for (int r2 = l2; r2 <= n; r2++)
//                {
//                    long long s2 = s[r2] - s[l2 - 1];
//                    mins = min(mins, abs(s1 - s2));
//                }
//            }
//        }
//    }
//    cout << mins;
//    return 0;
//}